1. Technical Field
The present invention pertains to wireless networks. In particular, the present invention pertains to detecting congestion within Ad-Hoc wireless networks and providing communications through the network that avoid the congestion to maintain network throughput.
2. Discussion of Related Art
An Ad-Hoc wireless network frequently includes nodes with a high concentration of traffic (e.g., packets, etc.). This traffic may be self-generated by a node with high traffic concentration, or be provided to that node from the network for relay to other network nodes. Network congestion tends to occur when these high concentration nodes are not bypassed, thereby resulting in packets being dropped and degradation of network throughput.
In order to avoid this situation, the congestion of a network node is measured and sent to other network nodes in order to enable routing to bypass the congested area. Congestion may be measured utilizing common techniques that measure queue utilization (i.e., the percentage of the storage capacity of a queue within a node being occupied by packets), packet drop rate (i.e., the rate packets are dropped from the node queue, or due to collisions), link failure rate (i.e., the link quality with respect to the percentage of packets that cannot be successfully transmitted using the link) and channel loading (i.e., the percentage a channel is utilized for sending traffic). Typically, congestion is sampled at a constant rate with the results being averaged.
The congested nodes are subsequently identified and bypassed based upon the congestion measurements. This may be accomplished by various conventional techniques. For example, a secondary route may be determined to bypass the primary routes that are congested. Further, several routes may be defined concurrently between source and destination nodes. When one of these routes is congested, another route may be utilized. Moreover, the congestion metric may be piggybacked within the transmission of the routing table (i.e., distance vector routing) or within the transmission of a Link State Advertisement (LSA) (i.e., link-state based routing).
However, the techniques described above suffer from several disadvantages. In particular, the congestion measurements described above may not provide an accurate measurement of true congestion. For example, the queue utilization measurement depends upon the size of the node queue. When the queue has a small storage capacity, small amounts of traffic may cause the queue utilization percentage to increase sufficiently to indicate congestion. If the queue has a large storage capacity, the queue may not be sufficiently filled and provide a low queue utilization percentage even though conditions include heavy traffic. The packet drop rate measurement is similarly connected to node queue size. A small queue storage capacity may easily drop packets even though there is no traffic congestion. A large queue storage capacity may store many packets, where no packets are dropped even though congestion has already occurred.
Further, the link failure rate may not accurately indicate the presence of congestion since link failure may be attributed to loss of radio connectivity due to mobility of network nodes. Link failure may further be attributed to a poor radio channel due to fading and multi-path interferences. Thus, a high link failure rate may not necessarily indicate occurrence of congestion.
In addition, channel loading is commonly measured by periodically sampling the channel. The channel loading value is one when the channel is busy, and zero if the channel is idle. This limitation of values is very coarse, and provides an inaccurate average due to the averaging of both busy and idle channel values. Further, the constant sampling for the measurement wastes processor power since measurements are performed for idle channels.
With respect to bypassing congested areas, determination of a secondary route (besides the primary routes) or plural routes requires the transmission of control packets to discover the routes. This significantly increases overhead and reduces the effectiveness of these techniques. Although a utilization measurement may be used to update the contention interval when a network node needs to access a communication channel using a Carrier Sense Multiple Access (CSMA) based protocol, this provides occasional or limited advantages based on simulation.
Conventional techniques send the congestion measurements within a broadcast of routing tables, or within a flood of Link State Advertisements (LSA). However, network nodes may not receive these items since congestion may have already occurred. This enables packets to be dropped due to the congestion.